package pers.qianyu.month_202012.date_20201212;

import org.junit.*;

import java.util.*;

/**
 * 42. 接雨水
 * https://leetcode-cn.com/problems/trapping-rain-water/
 *
 * @author mizzle rain
 * @date 2020-12-12 15:09
 */
public class Trap2 {
    /**
     * 单调栈
     */
    public int trap(int[] height) {
        if (height == null || height.length < 3) {
            return 0;
        }
        int res = 0;
        Stack<Integer> st = new Stack<>();
        for (int cur = 0; cur < height.length; cur++) {
            while (!st.isEmpty() && height[st.peek()] < height[cur]) {
                int mid = st.pop();
                if (st.isEmpty()) {
                    continue;
                }
                int h = Math.min(height[cur], height[st.peek()]) - height[mid];
                int w = cur - st.peek() - 1;
                res += h * w;
            }
            st.push(cur);
        }
        return res;
    }

    @Test
    public void test1() {
        int[] arr = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        int result = new Trap2().trap(arr);
        System.out.println("result = " + result);
    }
}
